// 给定一个未排序的整数数组nums，要求找出其中没有出现的最小的正整数，要求实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案
// 思路，哈希表
// 需要常数空间，那只能将数组作为哈希表，一个长度为n的哈希表，对应存储[1, n+1]之间，其中有个缺失的正整数

function firstMissingPositive(nums) {
    for (let i = 0; i < nums.length; i++) {
        // 数组作为map，只能存储n即为数组的长度大小
        if (nums[i] >= 1 && nums[i] <= nums.length && nums[i] !== nums[nums[i] - 1]) {
            // 这里不要图省事，把索引单独赋值给index1和index2，交换位置的[] = []这种语法特别容易出诡异的问题
            let index1 = i;
            let index2 = nums[i] - 1;
            [nums[index1], nums[index2]] = [nums[index2], nums[index1]]
        }
    }
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i + 1) {
            return i + 1
        }            
    }
    return nums.length + 1
}
let nums = [3,4,9,1, -1,1,2]
console.log(firstMissingPositive(nums))